package Year22_Month06.day21;

import java.util.ArrayList;
import java.util.List;

//前序遍历，不知道哪里错了，诶，停停
public class 二叉树的最近公共祖先 {
    //这样把，用一个链表，来保存对应的路径，然后两边两个对应的链表。
    List<TreeNode> list1 = new ArrayList<>();//用来存储第一个节点的路径
    List<TreeNode> list2 = new ArrayList<>();//用来存储第二个节点的路径
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //咋说呢，回溯算法？那我该咋写呢？
        solve1(root,new ArrayList<>(),p);
        solve2(root,new ArrayList<>(),q);
        for (int i = 0; i < list1.size(); i++) {
            for (int j = 0; j < list2.size(); j++) {
                if(list1.get(i) == list2.get(j)) return list1.get(i);
            }
        }
        return null;
    }

    public void solve1(TreeNode root,List<TreeNode> list,TreeNode target){
        if(root == null) return;
        if(root == target){
            list.add(root);
            list1 = list;
            return;
        }
        list.add(root);
        solve1(root.left,list,target);
        solve1(root.right,list,target);
    }
    public void solve2(TreeNode root,List<TreeNode> list,TreeNode target){
        if(root == null) return;
        if(root == target){
            list.add(root);
            list2 = list;
            return;
        }
        list.add(root);
        solve2(root.left,list,target);
        solve2(root.right,list,target);
    }
}
